Back نظرية التشغيل الذاتي Arabic Avtomatlar nəzəriyyəsi Azerbaijani Teoria d'autòmats Catalan Teorie automatů Czech Automatentheorie German Θεωρία αυτομάτων Greek Automata theory English Teoría de autómatas Spanish نظریه ماشینها Persian Automaattiteoria Finnish
Teorija automata[1] je dio teoretske informatike, čiji je zadatak proučavanje automata i problema, kojim se takvi automati bave.
Ova teorija je važna alatka u teorijama proračuna i kompleksiteta. Praktično se upotrebaljava kod izrade programskih prevodilaca (engl.: compiler) kao što su leksikalni skener (leksera) i parser.
Teorija automata je usko povezana sa teorijom formalnog jezika. U ovom kontekstu, automati se koriste kao konačni prikazi formalnih jezika koji mogu biti beskonačni. Automati se često klasifikuju prema klasi formalnih jezika koje mogu prepoznati, kao u Chomsky hijerarhiji, koja opisuje odnos ugniježđenja između glavnih klasa automata. Automati igraju glavnu ulogu u teoriji računanja, konstrukciji kompajlera, umjetnoj inteligenciji, raščlanjivanju i formalnoj verifikaciji.
Teorija apstraktnih automata razvijena je sredinom 20. stoljeća u vezi s konačnim automatima.[2] Teorija automata se u početku smatrala granom teorije matematičkih sistema, proučavajući ponašanje sistema diskretnih parametara. Rani rad u teoriji automata razlikovao se od prethodnog rada na sistemima korišćenjem apstraktne algebre za opisivanje informacionih sistema, a ne diferencijalnog računa za opisivanje materijalnih sistema.[3] Teoriju pretvarača konačnog stanja razvile su različite istraživačke zajednice pod različitim nazivima.[4] Raniji koncept Turingove mašine je takođe bio uključen u disciplinu zajedno sa novim oblicima automata sa beskonačnim stanjem, kao što su automati za spuštanje.
- ^ "Basics of Automata Theory". cs.stanford.edu. Pristupljeno 2024-08-20.
- ^ Mahoney, Michael S. "The Structures of Computation and the Mathematical Structure of Nature". The Rutherford Journal. Pristupljeno 7 June 2020.
- ^ Booth, Taylor (1967). Sequential Machines and Automata Theory. New York: John Wiley & Sons. str. 1-13. ISBN 0-471-08848-X.
- ^ Ashby, William Ross (January 15, 1967). "The Place of the Brain in the Natural World" (PDF). Currents in Modern Biology. 1 (2): 95–104. doi:10.1016/0303-2647(67)90021-4. PMID 6060865. Arhivirano s originala (PDF), 2023-06-04. Pristupljeno 2021-03-29.: "The theories, now well developed, of the "finite-state machine" (Gill, 1962), of the "noiseless transducer" (Shannon and Weaver, 1949), of the "state-determined system" (Ashby, 1952), and of the "sequential circuit", are essentially homologous."